
/**
 * 
 * 整数编码
 * 
 * 题目描述

实现一种整数编码方法，使得待编码的数字越小，编码后所占用的字节数越小。

编码规则如下:

编码时7位一组，每个字节的低7位用于存储待编码数字的补码
字节的最高位表示后续是否还有字节，置1表示后面还有更多的字节，置0表示当前字节为最后一个字节。
采用小端序编码，低位和低字节放在低地址上。
编码结果按16进制数的字符格式输出，小写字母需转换为大写字母
输入描述
输入的为一个字符串表示的非负整数

输出描述
输出一个字符串，表示整数编码的16进制码流

备注
待编码的数字取值范围为[0，1<<64 - 1]

用例
输入	0
输出	00
说明	输出的16进制字符，不足两位的前面补0，如00、01、02。
输入	100
输出	64
说明	
100的二进制表示为0110 0100，只需要一个字节进行编码;
字节的最高位置0，剩余7位存储数字100的低7位 (110 0100) ，所以编码后的输出为64。
输入	1000
输出	E807
说明	
1000的二进制表示为0011 1110 1000，至少需要两个字节进行编码;
第一个字节最高位置1，剩余的7位存储数字1000的第一个低7位 (1101000)，所以第一个字节的二进制为1110 1000，即E8;
第二个字节最高位置0，剩余的7位存储数字1000的第二个低7位 (0000111)，所以第一个字节的二进制为0000 0111，即07;
采用小端序编码，所以低字节E8输出在前，高字节07输出在后。

 * 
 */

import java.util.Scanner;

/**
  * 
  题目解析
本题有两种解题思路：

解法一：位运算
解法二：字符串解析
解法一：位运算

编码时7位一组，每个字节的低7位用于存储待编码数字的补码
如何获取一个数的二进制形式下最低七位？

我们通过将一个整数 num 和二进制数 0b01111111 进行按位与（&）运算，运算结果即为 num 二进制形式下低七位的值。

比如 num = 1000 的二进制形式如下：



1000 二进制形式下的低七位是：0011 1110 1000

1000 & 0b01111111 的结果也是：0110 1000



按位与运算的特点是：进行运算的两个数，对应位都为1，结果对应位才为1，否则为0。大家可以思考一下，为什么一个数 和 0b01111111 进行按位与&运算，会得到该数的低7位。
字节的最高位表示后续是否还有字节，置1表示后面还有更多的字节，置0表示当前字节为最后一个字节。
当我们获得 num 二进制形式的低7位后，如何判断 num 二进制形式是否还有剩余位呢？

此时可以使用二进制的右移运算， num >> 7，如果 num 右移7位后结果大于0，则说明还有剩余位。

此时我们要给之前读取的低7位最前补一个'1'

七位二进制 110 1000 其实和 八位二进制 0110 1000 是等价，相当于去除了前导0。但是实际运算时，还是基于八位二进制进行的。
那么给七位二进制 110 1000 前面补0，其实就等价于，如何让八位二进制 0110 1000 的最高位从0变1，其余位的值不变。

这里我们可以使用按位或 | 运算，即 0110 1000 | 1000 0000 == 1110 10000

按位或运算的特点是：进行运算的两个数，对应位只要有一个为1，则结果对应位为1，否则为0。大家可以根据按位或运算的特定，理解一下为什么一个八位二进制数 和 1000 0000 按位或运算后，可以将最高位变为1。
解法二：字符串解析

首先将输入的十进制数转为二进制字符串binStr，然后基于binStr“倒序”每7位一段，以用例3画图说明：



如果当前“段”的左边还有后续段，那么当前“段”需要在头部追加“1”形成新字节，如上图黄色段，由于其左边还有，则最终得到的新字节字符串是："1" + "1101000"，新字节字符串转化为十六进制后为E8



如果当前”段“不足7位，或者左边没有后续段了，那么当前”段“需要在头部追加”0“形成新字节（其实也可以不加），如上图绿色段，由于其左边没有后续段了，则最终得到的新字节字符串是：”0“ + ”00111“，新字节字符串转化为16进制后为7



对于不足两位的16进制，要在前面补足0
  */
public class 整数编码 {
    
    private static long num;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
 
        num = sc.nextLong();

        //doBit();

        doStrSpilt();

    }

    private static void doBit(){

        StringBuilder sb = new StringBuilder();
 
        do {
            // 编码时7位一组，每个字节的低7位用于存储待编码数字的补码
            long lowBit = num & 0b01111111; // 按位与运算, 获取 num 的低7位
 
            // lowBit的最高位表示后续是否还有字节，置1表示后面还有更多的字节，置0表示当前字节为最后一个字节。
            if (num >> 7 > 0) { // num 右移7位后, 若结果大于0, 则说明后面还有字节
                lowBit |= 0b10000000; // 按位或运算, 将lowBit最高位置1
            }
 
            // 编码结果按16进制数的字符格式输出，小写字母需转换为大写字母
            String hex = Long.toHexString(lowBit).toUpperCase();
 
            if (hex.length() == 1) {
                hex = "0" + hex;
            }
 
            sb.append(hex);
 
            // 右移运算移除num的低七位
            num >>= 7;
        } while (num != 0);
 
        System.out.println(sb);

    }

    private static void doStrSpilt(){
        String bin = Long.toBinaryString(num);
 
        StringBuilder ans = new StringBuilder();
     
        int end = bin.length();
        while (end - 7 > 0) {
          ans.append(getHexString("1" + bin.substring(end - 7, end)));
          end -= 7;
        }
     
        if (end >= 0) {
          ans.append(getHexString(bin.substring(0, end)));
        }
     
        System.out.println(ans.toString());
      }
     
      public static String getHexString(String binStr) {
        String hexStr = Integer.toHexString(Integer.parseInt(binStr, 2));
        if (hexStr.length() == 1) hexStr = "0" + hexStr;
        return hexStr.toUpperCase();
      }
}
